In iterative matrix algebra, we require a rigorous mathematical framework to quantify the "size" of vectors and matrices. These metrics allow us to determine if an approximation is approaching the true solution. Vector and matrix norms map high-dimensional arrays to non-negative real numbers while maintaining specific algebraic properties that bound errors and guarantee convergence.
The Axiomatic Foundation of Norms
Definition 7.1: Vector Norm
A vector norm $\|\cdot\|$ on $\mathbb{R}^n$ must satisfy four criteria:
- Non-negativity: $\|\mathbf{x}\| \geq 0$
- Definiteness: $\|\mathbf{x}\| = 0 \iff \mathbf{x} = \mathbf{0}$
- Absolute Homogeneity: $\|\alpha \mathbf{x}\| = |\alpha| \|\mathbf{x}\|$
- Triangle Inequality: $\|\mathbf{x} + \mathbf{y}\| \leq \|\mathbf{x}\| + \|\mathbf{y}\|$
Primary Metrics: $l_2$ and $l_\infty$
According to Definition 7.2, the most critical norms for numerical analysis are:
- Euclidean Norm ($l_2$): $\|\mathbf{x}\|_2 = \{ \sum_{i=1}^n x_i^2 \}^{1/2}$. Geometrically, the shortest distance from the origin.
- Maximum Norm ($l_\infty$): $\|\mathbf{x}\|_\infty = \max_{1 \leq i \leq n} |x_i|$. This captures the single largest component magnitude.
These definitions allow us to define the distance between an exact solution $\mathbf{x}$ and an approximation $\mathbf{y}$ as $\|\mathbf{x} - \mathbf{y}\|$ (Definition 7.4).
Matrix Norms and Induced Magnification
A matrix norm adds a fifth "sub-multiplicative" property (Definition 7.8): $\|A B\| \leq \|A\|\|B\|$.
Theorem 7.11: The Maximum Row Sum
For an $n \times n$ matrix $A$, the natural $l_\infty$ norm is calculated as the maximum of the absolute row sums:
$$\|A\|_{\infty} = \max_{1 \leq i \leq n} \sum_{j=1}^{n} |a_{ij}|$$
Worked Example: Vector & Matrix Calculation
Consider $\mathbf{x} = (-1, 1, -2)^t$ and $A = \begin{bmatrix} 1 & 2 & -1 \\ 0 & 3 & -1 \\ 5 & -1 & 1 \end{bmatrix}$.
Vector Norms
$\|\mathbf{x}\|_\infty = \max(|-1|, |1|, |-2|) = 2$.$\|\mathbf{x}\|_2 = \sqrt{(-1)^2 + (1)^2 + (-2)^2} = \sqrt{6} \approx 2.449$.
Matrix $l_\infty$ Norm
Row 1: $|1|+|2|+|-1|=4$Row 2: $|0|+|3|+|-1|=4$
Row 3: $|5|+|-1|+|1|=7$
Result: $\|A\|_\infty = 7$.
šÆ Core Principle
While the specific 'shape' of magnitude changes between norms, Theorem 7.7 guarantees equivalence: convergence in the $l_\infty$ norm implies convergence in the $l_2$ norm and vice versa.
$\|\mathbf{x}\|_\infty \leq \|\mathbf{x}\|_2 \leq \sqrt{n}\|\mathbf{x}\|_\infty$